package com.zhz.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 496. 下一个更大元素 I
 * nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
 * 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
 * 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
 * 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
 * <p>
 * 示例 1：
 * 输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
 * 输出：[-1,3,-1]
 * 解释：nums1 中每个值的下一个更大元素如下所述：
 * - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
 * - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
 * - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
 * <p>
 * 示例 2：
 * 输入：nums1 = [2,4], nums2 = [1,2,3,4].
 * 输出：[3,-1]
 * 解释：nums1 中每个值的下一个更大元素如下所述：
 * - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
 * - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
 * <p>
 * 提示：
 * 1 <= nums1.length <= nums2.length <= 1000
 * 0 <= nums1[i], nums2[i] <= 104
 * nums1和nums2中所有整数 互不相同
 * nums1 中的所有整数同样出现在 nums2 中
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/next-greater-element-i
 */
public class NextGreaterElementI496 {

    public static void main(String[] args) {
        NextGreaterElementI496 m = new NextGreaterElementI496();
        int[] nums1 = {2, 4};
        int[] nums2 = {1, 2, 3, 4, 5, 8, 6, 7};
        int[] result = m.nextGreaterElement1(nums1, nums2);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 先自己实现一遍  暴力破解
     * 题目不要理解错了，
     * 指的是当下元素接下来到数组结束的时候的第一个比当前元素大的
     * 不是单纯的j+1就行了
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = -1;
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]) {
                    //先找到相同的元素，接下来需要查早nums2数组里面index = j+1 开始的第一次出现的比nums[j]大的值
                    for (int k = j + 1; k < nums2.length; k++) {
                        if (nums2[k] > nums2[j]) {
                            result[i] = nums2[k];
                            break;
                        }
                    }
                }
            }
        }
        return result;
    }


    /**
     * 使用stack来解决
     * 官方解法，先从后往前遍历nums2数组，获取每一个值之后的最大值,然后将结果放到hashMap里面<curr,nextMax>，
     * 此时遍历nums1数组，取出当前值，然后再通过hashmap key 取出下一个最大值
     * <p>
     * {1, 2, 3, 4, 5, 8, 6, 7}
     */
    public int[] nextGreaterElementStack(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = nums2.length - 1; i >= 0; i--) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        for (int i = 0; i < nums1.length; i++) {
            result[i] = map.get(nums1[i]);
        }
        return result;
    }

    /**
     * 另一种暴力解法
     */
    public int[] nextGreaterElement1(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        int nextMax = 0;
        for (int i = 0; i < nums1.length; i++) {
            int j = nums2.length - 1;
            while (j >= 0 && nums2[j] != nums1[i]) {
                if (nums2[j] > nums1[i]) {
                    nextMax = nums2[j];
                }
                j -= 1;
            }
            result[i] = nextMax;
        }
        return result;
    }


}
